class Solution:
    def canChoose(self, groups: list, nums: list) -> bool:
        def buildNxt(p: list):
            nxt = [0]
            x = 1
            now = 0
            while x < len(p):
                if p[now] == p[x]:
                    x += 1
                    now += 1
                    nxt.append(now)
                elif now > 0:
                    now = nxt[now-1]
                else:
                    x += 1
                    nxt.append(0)
            return nxt

        def search(arr: list, p: list, nxt: list) -> int:
            tar = 0
            pos = 0
            while tar < len(arr):
                if arr[tar] == p[pos]:
                    tar += 1
                    pos += 1
                elif pos > 0:
                    pos = nxt[pos-1]
                else:
                    tar += 1

                if pos == len(p):
                    return tar - pos
            return -1

        nxts = []
        for group in groups:
            nxts.append(buildNxt(group))
        cur = 0
        for i in range(len(groups)):
            if cur == len(nums):
                return False
            index = search(nums[cur:], groups[i], nxts[i])
            if index < 0:
                return False
            cur = index+len(groups[i])

        return True
